package sort.bubble;

/**
 * 冒泡、插入、选择 排序
 * <p>
 * 冒泡 < 选择 < 插入
 * <p>
 * 数据量上10w 就很慢了。
 * <p>
 * Bubble Sort->
 * 170416
 * Insert Sort->
 * 7743
 * Select Sort->
 * 27085
 *
 * @author xushijian
 * @date 2021/07/28 9:31
 */
public class BubbleSort {

    public static void main(String[] args) {

        int[] nums = new int[1000];
        // bubble Sort
        long start1 = System.currentTimeMillis();
        //执行10次，避免偶合性
        for (int k = 0; k < 10; k++) {
            for (int j = 0; j < nums.length; j++) {
                nums[j] = (int) (Math.random() * 10000);
            }
            bubbleSortNew(nums);
            //bubbleSort(nums);
        }
        long end1 = System.currentTimeMillis();
        System.out.println("Bubble Sort->");
        System.out.println(end1 - start1);
        //insert Sort
        long start2 = System.currentTimeMillis();
        for (int k = 0; k < 10; k++) {
            for (int j = 0; j < nums.length; j++) {
                nums[j] = (int) (Math.random() * 10000);
            }
            insertSort(nums);
        }
        long end2 = System.currentTimeMillis();
        System.out.println("Insert Sort->");
        System.out.println(end2 - start2);
        //select sort
        long start3 = System.currentTimeMillis();
        for (int k = 0; k < 10; k++) {
            for (int j = 0; j < nums.length; j++) {
                nums[j] = (int) (Math.random() * 10000);
            }
            selectSort(nums);
        }
        long end3 = System.currentTimeMillis();
        System.out.println("Select Sort->");
        System.out.println(end3 - start3);
    }

    /**
     * 冒泡排序（相邻数据比较）
     *
     * @param nums
     */
    public static void bubbleSortNew(int[] nums) {

        int length = nums.length, temp;
        boolean flag;
        for (int i = 0; i < length; i++) {
            flag = true;
            for (int j = 1; j < length; j++) {
                if (nums[j - 1] > nums[j]) {
                    temp = nums[j - 1];
                    nums[j - 1] = nums[j];
                    nums[j] = temp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

    /**
     * 冒泡排序（相邻数据比较）
     *
     * @param nums
     */
    public static void bubbleSort(int[] nums) {

        int length = nums.length;
        for (int i = 0; i < length; i++) {
            for (int j = 1; j < length; j++) {
                if (nums[j - 1] > nums[j]) {
                    int temp = nums[j - 1];
                    nums[j - 1] = nums[j];
                    nums[j] = temp;
                }
            }
        }
    }

    /**
     * 1 9 6 2 4 3
     * 插入数据排序  （一轮可能会换多个）
     * <p>
     * 核心： 指定节点（用插入节点与节点以前的数据进行排序）
     * <p>
     * insertNode 节点不变，然后与之前的值进行比较，insertNode小于或等于，则与其他交换，再次循环。
     *
     * @param nums 集合
     */
    public static void insertSort(int[] nums) {
        int insertNode;
        int j;
        for (int i = 1; i < nums.length; i++) {
            insertNode = nums[i];
            j = i - 1;
            while (j >= 0 && insertNode < nums[j]) {
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = insertNode;
        }
    }

    /**
     * 选择排序  (一轮只换一个）
     * <p>
     * 核心：  确定当前节点，然后索引++节点后面排序，然后替换。
     *
     * @param nums 集合
     */
    public static void selectSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int pos = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[pos] > nums[j]) {
                    pos = j;
                }
            }
            if (pos != i) {
                int temp = nums[i];
                nums[i] = nums[pos];
                nums[pos] = temp;
            }
        }
    }
}